/*
 * @lc app=leetcode.cn id=648 lang=typescript
 *
 * [648] 单词替换
 */

// @lc code=start
function replaceWords(dictionary: string[], sentence: string): string {
  // 利用哈希表存储词根
  const map = new Set(dictionary);
  const words = sentence.split(' ');

  for (let i = 0; i < words.length; i++) {
    const word = words[i];
    for (let j = 0; j < word.length; j++) {
      const root = word.substring(0, j + 1);
      // 找到词根，替换
      if (map.has(root)) {
        words[i] = root;
        break;
      }
    }
  }

  return words.join(' ');
}
// @lc code=end
